'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-06-27 09:40:55
'''
'''
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
提示：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

'''

# 时间和空间的限制，致使可以采用原地hash的方法，即将v放在v-1的位置去
from typing import List
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            # 循环，将元素放入它对应的位置去。这个循环有选择性，并不会增加时间复杂度
            while nums[i]>0 and nums[i]<len(nums) and nums[nums[i]-1] != nums[i]:
                tmp = nums[i]
                nums[tmp-1], nums[i] = nums[i], nums[tmp-1]
        # print(nums)
        for i, v in enumerate(nums):
            if v != i+1:
                return i+1
        return len(nums)+1

if __name__ == "__main__":
    solution = Solution()
    nums = [11,1,6,11,5,5,-6,9,-3,9,5,4,2,-8,16,-6,-4,2,3]
    print(solution.firstMissingPositive(nums))